85. Maximal Rectangle
Hard

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

 

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = []
Output: 0

Example 3:

Input: matrix = [["0"]]
Output: 0

Example 4:

Input: matrix = [["1"]]
Output: 1

Example 5:

Input: matrix = [["0","0"]]
Output: 0

 

Constraints:

  • rows == matrix.length
  • cols == matrix[i].length
  • 0 <= row, cols <= 200
  • matrix[i][j] is '0' or '1'.
Accepted
234,175
Submissions
583,300
Seen this question in a real interview before?
Companies

Average Rating: 4.41 (85 votes)

Premium

Solution


Approach 1: Brute Force

Algorithm

Trivially we can enumerate every possible rectangle. This is done by iterating over all possible combinations of coordinates (x1, y1) and (x2, y2) and letting them define a rectangle with the coordinates being opposite corners. This is too slow to pass all test cases.

Complexity Analysis

  • Time complexity : O(N3M3)O(N^3M^3), with N being the number of rows and M the number of columns.

    Iterating over all possible coordinates is O(N2M2)O(N^2M^2), and iterating over the rectangle defined by two coordinates is an additional O(NM)O(NM). O(NM)O(N2M2)=O(N3M3)O(NM) * O(N^2M^2) = O(N^3M^3).

  • Space complexity : O(1)O(1).


Approach 2: Dynamic Programming - Better Brute Force on Histograms

Algorithm

We can compute the maximum width of a rectangle that ends at a given coordinate in constant time. We do this by keeping track of the number of consecutive ones each square in each row. As we iterate over each row we update the maximum possible width at that point. This is done using row[i] = row[i - 1] + 1 if row[i] == '1'.

Current
1 / 10

Once we know the maximum widths for each point above a given point, we can compute the maximum rectangle with the lower right corner at that point in linear time. As we iterate up the column, we know that the maximal width of a rectangle spanning from the original point to the current point is the running minimum of each maximal width we have encountered.

We define:

maxWidth=min(maxWidth,widthHere)maxWidth = min(maxWidth, widthHere)

curArea=maxWidth(currentRoworiginalRow+1)curArea = maxWidth * (currentRow - originalRow + 1)

maxArea=max(maxArea,curArea)maxArea = max(maxArea, curArea)

The following animation makes this more clear. Given the maximal width of all points above it, let's calculate the maximum area of any rectangle at the bottom yellow square:

Current
1 / 7

Repeating this process for every point in our input gives us the global maximum.

Note that our method of precomputing our maximum width essentially breaks down our input into a set of histograms, with each column being a new histogram. We are computing the maximal area for each histogram.

Histograms

As a result, the above approach is essentially a repeated use of the better brute force approach detailed in 84 - Largest Rectangle in Histogram.

Complexity Analysis

  • Time complexity : O(N2M)O(N^2M). Computing the maximum area for one point takes O(N)O(N) time, since it iterates over the values in the same column. This is done for all NMN * M points, giving O(N)O(NM)=O(N2M)O(N) * O(NM) = O(N^2M).

  • Space complexity : O(NM)O(NM). We allocate an equal sized array to store the maximum width at each point.


Approach 3: Using Histograms - Stack

Algorithm

In the previous approach we discussed breaking the input into a set of histograms - one histogram representing the substructure at each column. To compute the maximum area in our rectangle, we merely have to compute the maximum area of each histogram and find the global maximum (note that the below approach builds a histogram for each row instead of each column, but the idea is still the same).

Since Largest Rectangle in Histogram is already a problem on leetcode, we can just borrow the fastest stack-based solution here and apply it onto each histogram we generate. For an in-depth explanation on how the Largest Rectangle in Histogram algorithm works, please use the links above.

Note that the code under the function leetcode84 is a direct copy paste from the final solution in 84 - Largest Rectangle in Histogram.

Complexity Analysis

  • Time complexity : O(NM)O(NM). Running leetcode84 on each row takes M (length of each row) time. This is done N times for O(NM)O(NM).

  • Space complexity : O(M)O(M). We allocate an array the size of the the number of columns to store our widths at each row.


Approach 4: Dynamic Programming - Maximum Height at Each Point

Intuition

Imagine an algorithm where for each point we computed a rectangle by doing the following:

  • Finding the maximum height of the rectangle by iterating upwards until a 0 is reached

  • Finding the maximum width of the rectangle by iterating outwards left and right until a height that doesn't accommodate the maximum height of the rectangle

For example finding the rectangle defined by the yellow point:

Current
1 / 6

We know that the maximal rectangle must be one of the rectangles constructed in this manner.

Given a maximal rectangle with height h, left bound l, and right bound r, there must be a point on the interval [l, r] on the rectangle's base where the number of consecutive ones (height) above the point is <=h. If this point exists, then the rectangle defined by the point in the above manner will be the maximal rectangle, as it will reach height h iterating upward and then expand to the bounds of [l, r] as all heights within those bounds must accommodate h for the rectangle to exist.

If this point does not exist, then the rectangle cannot be maximum, as you would be able to create a bigger rectangle by simply increasing the height of original rectangle, since all heights on the interval [l, r] would be greater than h.

As a result for each point you only need to compute h, l, and r - the height, left bound, and right bound of the rectangle it defines.

Using dynamic programming, we can use the h, l, and r of each point in the previous row to compute the h, l, and r for every point in the next row in linear time.

Algorithm

Given row matrix[i], we keep track of the h, l, and r of each point in the row by defining three arrays - height, left, and right.

height[j] will correspond to the height of matrix[i][j], and so on and so forth with the other arrays.

The question now becomes how to update each array.

Height:

This one is easy. h is defined as the number of continuous ones in a line from our point. We explored how to compute this in Approach 2 in one row with:

row[j] = row[j - 1] + 1 if row[j] == '1'

We can just make a minor modification for it to work for us here:

new_height[j] = old_height[j] + 1 if row[j] == '1' else 0

Left:

Consider what causes changes to the left bound of our rectangle. Since all instances of zeros occurring in the row above the current one have already been factored into the current version of left, the only thing that affects our left is if we encounter a zero in our current row.

As a result we can define:

new_left[j] = max(old_left[j], cur_left)

cur_left is one greater than rightmost occurrence of zero we have encountered. When we "expand" the rectangle to the left, we know it can't expand past that point, otherwise it'll run into the zero.

Right:

Here we can reuse our reasoning in left and define:

new_right[j] = min(old_right[j], cur_right)

cur_right is the leftmost occurrence of zero we have encountered. For the sake of simplicity, we don't decrement cur_right by one (like how we increment cur_left) so we can compute the area of the rectangle with height[j] * (right[j] - left[j]) instead of height[j] * (right[j] + 1 - left[j]).

This means that technically the base of the rectangle is defined by the half-open interval [l, r) instead of the closed interval [l, r], and right is really one greater than right boundary. Although the algorithm will still work if we don't do this with right, doing it this way makes the area calculation a little cleaner.

Note that to keep track of our cur_right correctly, we must iterate from right to left, so this is what is done when updating right.

With our left, right, and height arrays appropriately updated, all that there is left to do is compute the area of each rectangle.

Since we know the bounds and height of rectangle j, we can trivially compute it's area with height[j] * (right[j] - left[j]), and change our max_area if we find that rectangle j's area is greater.

The code and idea for the above solution originates from user morrischen2008.

Complexity Analysis

  • Time complexity : O(NM)O(NM). In each iteration over N we iterate over M a constant number of times.

  • Space complexity : O(M)O(M). M is the length of the additional arrays we keep.



Written by @alwinpeng.

Report Article Issue

Comments: 32
sofeikov's avatar
Read More

I was so surprised when I actually needed this algorithm for a real-life task at work :D

186
Show 12 replies
Reply
Share
Report
chinanathan's avatar
Read More

the explain of solution 4 is very hard to understand. at least you should put down the definition of height, and left, and right

21
Reply
Share
Report
mirak's avatar
Read More

For approach 3, we don't need a 2D array here. A 1D array (heights) could do the job, so the space complexity could be reduced to O(M).
https://github.com/mirak94/Problem-Solving-Practice/blob/leetcode/Leetcode/src/com/mirak/leetcode/individual/hard/MaximalRectangle.java

9
Show 2 replies
Reply
Share
Report
sase1017's avatar
Read More

Can anyone understand solution 4? It seems kind of understandable by syntax and high level,
but when looking into the pointer movement, it just can't make sense.

7
Reply
Share
Report
sh0gg0th's avatar
Read More

@alwinpeng Approach 2 causes a TLE in Python. Adding early termination (no need to continue searching upwards once max width becomes zero), we can make it pass:

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        maxarea = 0

        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == '0': continue

                # compute the maximum width and update dp with it
                width = dp[i][j] = dp[i][j-1] + 1 if j else 1

                # compute the maximum area rectangle with a lower right corner at [i, j]
                for k in range(i, -1, -1):
                    width = min(width, dp[k][j])
                    # terminate
                    if width == 0: break
                    maxarea = max(maxarea, width * (i-k+1))
        return maxarea

5
Reply
Share
Report
RaBhaSa's avatar
Read More

For the third solution, to be precise, the time complexity is O(N* 2M), I was initially confused and was thinking the time complexity should be O(NM^2), but realised that the second iteration for each row is outside the first iteration for each row, that sums up to total time complexity of O(N*2M)...just posting, if it could help anyone with similar doubt...

10
Show 1 reply
Reply
Share
Report
uncle_iroh's avatar
Read More

Can someone explain why approach 2 and 4 are called DP? They both seem like brute force optimizations using some pre-computation, but that's where the similarity with a typical DP problem ends.

I do not see a recursive substructure or a recurrence relation. If such a recurrence relation existed, a top down DP solution would be possible.

All I see is iteration over lots of possible rectangles. The order of checking is smart, so this is more like Kadane's algorithm in 2D rather than DP.

4
Reply
Share
Report
veecos's avatar
Read More

Solution 2 in Python leads to TLE. Please update this in the solution so that people are aware and don't need to figure out on their own.

3
Show 1 reply
Reply
Share
Report
QNXGZ's avatar
Read More

can't believe this is a high frequency question T_T

2
Show 1 reply
Reply
Share
Report
madno's avatar
Read More

There is another interesting dp solution.
This also runs in O(Row * Column) overall.
It's interesting because looking at the code it looks like O(Row * Column^2)
but actually each inner "for+while loop" runs in O(Column) time amortised.

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int R = matrix.length, C = R == 0 ? 0 : matrix[0].length;
        int[] cnt = new int[C], lw = new int[C], rw = new int[C];//lw = leftWidth, rw = rightWidth
        int ans = 0;
        for(int r = 0; r < R; ++r){
            for(int c = 0; c < C; ++c){//consecutive one length inside column c until row r
                cnt[c] = (cnt[c]+1)*(matrix[r][c]-'0');
            }
            for(int i = 0; i < C; ++i){//lw[i] width of rectangle with cnt[i] height to left, i-th column inclusive
                lw[i] = 1;
                while(i-lw[i] >= 0 && cnt[i-lw[i]] >= cnt[i]){
                    lw[i] += lw[i-lw[i]];
                }
            }
            for(int j = C-1; j >= 0; --j){//rw[j] width of rectangle with cnt[j] height to right, j-th column inclusive
                rw[j] = 1;
                while(j+rw[j] < C && cnt[j+rw[j]] >= cnt[j]){
                    rw[j] += rw[j+rw[j]];
                }
            }
            for(int i = 0; i < C; ++i){//search for new possible maximum rectangle area
                ans = Math.max(ans, (rw[i]+lw[i]-1)*cnt[i]);
            }
        }
        return ans;
    }
}

2
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
03/22/2021 08:40Accepted32 ms13.3 MBcpp
09/26/2020 20:38Accepted52 ms12.1 MBcpp
09/26/2020 20:37Runtime ErrorN/AN/Acpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.